
  #include "evolution.h"
  #include "mylib.h"
  
  
  class Variables built_ins;
  /* E' l'oggetto della classe Variables che contiene le informazioni sulle
     variabili built-in.
  */ 
  
  /******************************************************************
          Dichiarazione delle variabili esterne al file.
  ******************************************************************/


  // ******* Funzioni per la generazione di numeri casuali. *******
  extern int rnd(int low, int high);
  extern float rndreal(float low, float high);
  extern int flip(float prob);

  /******************************************************************
          Definizione delle procedure della classe POPULATION
   ******************************************************************/
  
  /*
  ----------------- Procedura dm_population -------------------------------
  *** Scritta il: 24/07/03
  E' la costruttrice della classe. E' vuota. 
  *** Ultima modifica:
  */   
  Population::Population()
  {
  
     return;
  }
  
    
  /*
  ----------------- Procedura Population -------------------------------
  *** Scritta il: 24/07/03
  E' una seconda costruttrice della classe. Il parametro N specifica il nu-
  mero di individui di cui e' normalmente costituita la popolazione.
  *** Ultima modifica:
  */   
  Population::Population(int N, Evolution *evo_ptr)
  {
     int i;


     // Si inizializza l'array dei puntatori agli individui.
     for (i=0; i < MAX_INDIVIDUALS; ++i)
        individuals[i] = NULL_INDIVIDUAL;
 
     /* Si inizializza il numero di individui che la popolazione dovra' con-
        tenere. */
     N_inds = N;
     
     /* Si inizializza il contatore del numero di individui attualmente con-
        tenuto nella popolazione. */
     ind_counter = 0;
     
     /* Si inizializza il puntatore all'oggetto della Classe Evolution che 
        ha generato la popolazione. */
     evolution = evo_ptr;   

     return;  
  }

 

  /*
  ----------------- procedura add_individual ------------------------------
  *** Scritta il:
  Aggiunge un nuovo individuo alla popolazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Population::add_individual(Individual *individual_ptr)
  {
     /* Si controlla se si eccede il numero di individui che la popolazione
        deve contenere. */
     if (ind_counter < N_inds)
       individuals[ind_counter++] = individual_ptr;
     else abort_message((char *) "Il numero di individui generati  ha superato \
		         il massimo consentito");

     return;
  }
  
  


  /*
  ----------------- procedura comp_data -----------------------------------
  *** Scritta il:
  Effettua dei calcoli relativi ad alcune grandezze della popolazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Population::comp_data()
  {
    int  i, tot_ind;
    double tmp_fitness;
    

    // Inizializzazione.
    tot_ind = 0;
    tot_fitness = 0.0;
    tot_fitness_inv = 0.0;

    for (i=0; i < ind_counter; ++i)
       // Si controlla che l'individuo non sia stato ucciso.   
       if (individuals[i]->alive)
       {
         // Si memorizza la fitness dell'individuo
         tmp_fitness = individuals[i]->give_fitness();
         // Si incrementa la fitness totale
         tot_fitness += tmp_fitness;

         /* Si incrementa la fitness totale inversa controllando che
            sia diversa da zero. */
         if (tmp_fitness != 0.0)
           tot_fitness_inv += 1.0 / tmp_fitness;
         else tot_fitness_inv += DBL_MAX;

         // Si incrementa il numero di individui validi
         tot_ind++;
       }
  

    // Si controlla che il numero di individui validi sia maggiore di zero.
    if (tot_ind)
      average_fit = tot_fitness / tot_ind;
    else abort_message((char *) "comp_average_fit: tutti gli individui sono stati \
                        uccisi!");

    return;
  }
  
  /*
  ----------------- procedura comp_vars -----------------------------------
  *** Scritta il:
  Effettua i calcoli relativi alle variabili di cui tenere conto.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Population::comp_vars(int vars_num, struct variable vars_vec[])
  {
    int  i, tot_ind, j;
    double tmp, min, max;

      
    // Si memorizzano i valori delle variabili dei migliori individui.
    for (i=0; i <vars_num; ++i)
       vars_vec[i].best_val = best->inner_vars[i];
       
    /* Si calcolano i valori medi su tutta la popolazione, per ognuna delle
       variabili. */
    for (i=0; i <vars_num; ++i)
    { 
       // Inizializzazione.
       tmp = 0.0;
       tot_ind = 0;
       min = max = individuals[0]->inner_vars[i];
       
       for (j=0; j < ind_counter; ++j)
          // Si calcola solo per gli individui ancora "vivi".
          if (individuals[j]->alive)    
          {
            tmp += individuals[j]->inner_vars[i];
            ++tot_ind;
            
            // Controllo del minimo.
            if (individuals[j]->inner_vars[i] < min)
              min = individuals[j]->inner_vars[i];
              
            // Controllo del massimo.
            if (individuals[j]->inner_vars[i] > max)
              max = individuals[j]->inner_vars[i];  
          }      
       
       // Calcolo della media.
       vars_vec[i].ave_val = tmp / tot_ind; 
       
       // Assegnazione di minimo e massimo.
       vars_vec[i].min_val = min;
       vars_vec[i].max_val = max;
    }        

   
    return;
  }



  /*
  ----------------- procedura update --------------------------------------
  *** Scritta il:
  Aggiorna tutti gli individui della classe ai quali sono stati applicati
  gli operatori di crossover e di mutazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Population::update()
  {
    register int i;

    /* Si aggiornano tutti gli individui della popolazione che sono ancora 
       vivi. */
    for (i=0; i < ind_counter; ++i)
       if (individuals[i]->alive) 
         individuals[i]->update();
         

     // Si chiama la procedura per il calcolo delle fitness degli individui.
     comp_fitnesses();
     
     
    return;
  }

  /*
  ----------------- procedura kill ----------------------------------------
  *** Scritta il:
  Distrugge gli individui della popolazione. La procedura inizializza con
  il puntatore nullo gli elementi dell'array di puntatori agli individui e
  a zero il numero di individui.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Population::kill()
  {
      register int i;

      
      
      // Cancellazione degli individui dalla popolazione.
      for (i=0; i < ind_counter; ++i)
	     individuals[i]->kill();
      
      
      // Inizializzazione del vettore di puntatori.
      for (i=0; i < ind_counter; ++i)
         individuals[i] = NULL_INDIVIDUAL;

      // Azzeramento del contatore degli individui. 
      ind_counter = 0;

      return;
  }

  /*
  ----------------- procedura comp_fitnesses ------------------------------
  *** Scritta il:
  Calcola la fitness degli individui della popolazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Population::comp_fitnesses()
  {
      register int i;


      // Calcola la fitness degli individui della popolazione. 
      for (i=0; i < ind_counter; ++i)      
         individuals[i]->comp_fitness();
          
        
     return;
  }

  /*
  ----------------- procedura improve --------------------------------------
  *** Scritta il:
  E' una procedura che puo' essere usata per migliorare gli individui della
  popolazione corrente. In pratica puo' essere usata per ibridizzare gli
  algoritmi. Quella di base e' vuota.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Population::improve()
  {

      return;
  }

  /*
  ----------------- procedura find_best -----------------------------------
  *** Scritta il:
  Trova il miglior individuo presente nella popolazione. IL parametro type
  specifica se il problema e' di massimizzazione o di minimizazzione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */ 
  Individual *Population::find_best(problem_types type)
  {
     int  first, better;
     register int i;
     
     /* Questo ciclo serve ad individuare il primo elemento della
        popolazione con fitness valida. */
     for (first=0; first < ind_counter; ++first)
        if (individuals[first]->alive)
          break;
     

     // Si controlla se tutti gli individui sono stati uccisi.
     if (first == ind_counter)
       abort_message ((char *) "Tutti gli elementi della popolazione sono stati \
       uccisi!");

     // ----- Ricerca del migliore per problemi di MINIMIZZAZIONE -----
     if (type == min_)
     {
       /* Il ciclo scandisce l'array che punta agli individui della popola-
          zione e trova quello con la fitness migliore. */
       better = first;

       for (i = first + 1; i < ind_counter; ++i)
	      if (individuals[i]->alive)
                if (individuals[i]->give_fitness() < individuals[better]->give_fitness())
	          better = i;
       
       /* Il miglior individuo trovato viene assegnato alla variabile
          best della classe che punta al migliore individuo della popolazi-
          one e viene ritornato anche come valore della funzione. */
       return best = individuals[better];
     }

     // ----- Ricerca del migliore per problemi di MASSIMIZZAZIONE -----
     if (type == max_)
     {
       /* Il ciclo scandisce l'array che punta agli individui della popola-
          zione e trova quello con la fitness migliore. */
       better = first;

       for (i = first + 1; i < ind_counter; ++i)
	      if (individuals[i]->alive)
            if (individuals[i]->give_fitness() > individuals[better]->give_fitness())
	          better = i;
                  

       /* Il miglior individuo trovato viene assegnato alla variabile best
          della classe che punta al migliore individuo della popolazione e
          viene ritornato anche come valore della funzione. */
       return best = individuals[better];
     }
  }

  /*
  ----------------- procedura select --------------------------------------
  *** Scritta il:
  Seleziona un individuo della popolazione. Se choose vale uni_distrib al-
  lora la procedura usa una distribuzione di tipo uniforme. Se invece usa
  wheel applica l'algoritmo della roulette wheel. Infine, se choose vale
  tourn si usa il tournment. Il parametro type specifica se il problema e'
  di minimazzazione o massimizzazione.
  *** Ultima modifiche: ore 11.00 del  1/07/03
  *** Tipi:
           1) E'stata inserita la roulette wheel per problemi di mini-
              mizzazione.
	       2) E'stata aggiunta la parte relativa allo Stochastic Uni-
	          versal Sampling.
           4/01/04
  *** Tipi:  E' stato aggiunto il parametro type. In questo modo la proce-
             dura e' piu' generale e puo' essere usata sia per problemi di
             minimizzazione che di massimizzazione. 
  */
  Individual *Population::select(choose_type choose, problem_types type)
  {
     int i, best_ptr, temp_ptr;
     double arrow, sector, tot_inv_fit;  /* tot_inv_fit e' la variabile che
            memorizza la somma della inverse delle fitness, e serve per la
             roulette wheel per problemi di minimizzazione. */
       

     // ------------ Implementazione della scelta RANDOM. -----------
     if (choose == rand_)
     {// Il ciclo do serve ad evitare gli individui uccisi.                  

       do temp_ptr = rnd(0, ind_counter - 1);
       while(!(individuals[temp_ptr]->alive));

       return individuals[temp_ptr];
     }

     // ------------ Implementazione della scelta truncation. -----------
     if (choose == trunc_)
     {
       int trunc_num =  ind_counter *evolution->give_trunc_size();
       // Il ciclo do serve ad evitare gli individui uccisi.
       do temp_ptr = rnd(0, trunc_num - 1);
       while(!(individuals[temp_ptr]->alive));

       return individuals[temp_ptr];
     }
     
     //--------- Implementazione della ROULETTE WHEEL ----------------
     if (choose == wheel)
     {
       sector = 0.0;

       /* Si assegna alla variabile arrow un numero tra 0.0 e 1.0 genera-
           to casualmente. */
       arrow = rndreal(0.0, 1.0);

       // --- Implementazione della roulette wheel per MINIMIZZAZIONE --
       if (type == min_)
       {
         for (i=0; i < ind_counter; ++i)
         /* Si controlla in quale "settore" della ruota e' finita la arrow.
            Ad ogni settore corrisponde un diverso individuo. */
            if(individuals[i]->alive) // Si considerano solo i "vivi".
            {
              sector +=  (1.0 / ((double) individuals[i]->give_fitness() -
                                  evolution->fitness->min)) /
                                  tot_fitness_inv;
              if (arrow < sector)
                return individuals[i];
            }

            if (arrow == 1.0)
              return individuals[ind_counter - 1];
       }
 
       // --- Implementazione della roulette wheel per MASSIMIZZAZIONE --
       if (type == max_)
       {
         for (i=0; i < ind_counter; ++i)
         /* Si controlla in quale "settore" della ruota e' finita la arrow.
            Ad ogni settore corrisponde un diverso individuo. */
            if(individuals[i]->alive) // Si considerano solo i "vivi". 
            {  
              sector +=  ((double) individuals[i]->give_fitness() )//-
                        //  evolution->fitness->min) / tot_fitness;
                        /tot_fitness;
              if (arrow < sector)
                return individuals[i];
            }

            if (arrow == 1.0)
              return individuals[ind_counter - 1];
       }
     }

     // ----------------- Implementazione del Tournment -------------------
     if (choose == tournment)
     {        
       // Il ciclo do serve ad evitare gli individui uccisi. 
       do best_ptr = rnd(0, ind_counter - 1);
       while(!(individuals[best_ptr]->alive));

       // --- Implementazione del tournment per MINIMIZZAZIONE --
       if (type == min_)
       {
         for (i=1; i < evolution->give_tourn_size(); ++i)
         {
            // Si saltano gli eventuali indidivui uccisi. 
            do temp_ptr = rnd(0, ind_counter - 1);
            while(!(individuals[temp_ptr]->alive));

            if (individuals[temp_ptr]->give_fitness() <
                individuals[best_ptr]->give_fitness())
	          best_ptr = temp_ptr;
	        else if (individuals[temp_ptr]->give_fitness() ==
	 	             individuals[best_ptr]->give_fitness())
		           if(flip(0.5))
                     best_ptr = temp_ptr;
         }
       }

       // --- Implementazione del tournment per MASSIMIZZAZIONE --
       if (type == max_)
       {
         for (i=1; i < evolution->give_tourn_size(); ++i)
         {
            // Si saltano gli eventuali individui uccisi.
            do temp_ptr = rnd(0, ind_counter - 1);
            while(!(individuals[temp_ptr]->alive));
	  
            if (individuals[temp_ptr]->give_fitness() >
                individuals[best_ptr]->give_fitness())
	          best_ptr = temp_ptr;
	        else if (individuals[temp_ptr]->give_fitness() ==
	 	             individuals[best_ptr]->give_fitness())
		           if(flip(0.5))
                     best_ptr = temp_ptr;
         }
       }

       return individuals[best_ptr];

       abort_message((char *) "Impossibile  selezionare gli individui della \
       		      popolazione, verificare  la prodedura \
		      Population::select");
     }

     //----- Implementazione dello Stochastic Universal Sampling --
     if (choose == stoc_uni)
     {
       abort_message((char *) "Al momento il SUS NON puo' essere utilizzato!");

       temp_ptr = rnd(0, evolution->sus_num);
     
       return stoc_uni_individuals[temp_ptr];
     }

  // FINE della procedura select
  }


  /*
  ----------------- procedura build_sus_array -----------------------------
  *** Scritta il: 1/7/03 ore 17.00
  Seleziona gli individui necessari all'applicazione dello Stochastic Uni-
  versal Sampling. Il parametro type specifica se il problema e' di mini-
  mizzazione o massimizzazione.
  */
  void Population::build_sus_array(problem_types type)
  {
    int curr_ind, stoc_ind_ptr, N;
    double sector, pointer;
    
     
    // Inizializzazione.
    curr_ind = 0;
    stoc_ind_ptr = 0;
    N = evolution->sus_num; /* E' il numero di individui da utilizzare per
                               il SUS. */

    /* Si saltano gli eventuali individui iniziali della popolazione 
       che sono stati uccisi. */
    while (!(individuals[curr_ind]->alive))
      ++curr_ind;

    // --- Implementazione del SUS per MINIMIZZAZIONE --
    if (type == min_)
    {
      // Ancora inizializzazione.
      sector = 1.0 / (individuals[curr_ind]->give_fitness() -
                      evolution->fitness->min);
      pointer = rndreal(0.0, tot_fitness_inv / N);

      // Applicazione dell'algoritmo SUS.
      while ((pointer < tot_fitness_inv) && (stoc_ind_ptr < N))
        if (sector >= pointer)
        {
	      stoc_uni_individuals[stoc_ind_ptr++] = individuals[curr_ind];
	      pointer += tot_fitness_inv / N;
        }
        else
        {
	      // Si saltano gli individui uccisi. 
	      do curr_ind++;
	      while ((!(individuals[curr_ind]->alive)) && 
	              (stoc_ind_ptr < N));

         sector += 1.0 / (individuals[curr_ind]->give_fitness() -
                          evolution->fitness->min);
        }
     }

     // --- Implementazione del SUS per MASSIMIZZAZIONE --
     if (type == max_)
    {
      // Inizializzazione.
      sector = individuals[curr_ind]->give_fitness() - evolution->fitness->min;
      pointer = rndreal(0.0, tot_fitness / N);

      // Applicazione dell'algoritmo SUS.
      while ((pointer < tot_fitness) && (stoc_ind_ptr < N))
        if (sector >= pointer)
        {
	      stoc_uni_individuals[stoc_ind_ptr++] = individuals[curr_ind];
	      pointer += tot_fitness /N;
        }
        else
        {
	      // Si saltano gli individui uccisi. 
	      do curr_ind++;
	      while ((!(individuals[curr_ind]->alive)) && 
	             (stoc_ind_ptr < N));

         sector += individuals[curr_ind]->give_fitness() -
                   evolution->fitness->min;
        }
     }

     // Si controlla se e' stato costruito tutto l'array.
     if (stoc_ind_ptr < N)
       abort_message((char *) "build_sus_array: l'array per il SUS contiene solo %d\
                     individui", stoc_ind_ptr);


    return;
  }

   /*
  ----------------- procedura comp_score------------------------------
  *** Scritta il: 15/9/03
  Calcola lo score dell'individuo passato come parametro.
  *** Ultima modifica: 
  */
  void Population::comp_score(int ind_index, problem_types type)
  {
    int i, j, q, s_val = 0;
    
    q = evolution->give_tourn_size();
      
   for (i=0; i < q; ++i) 
   {
      do j = rnd(0, ind_counter - 1);
      while (j == ind_index);
      
     if (type == max_) {
       if (individuals[ind_index]->give_fitness() >= 
           individuals[j]->give_fitness())
         s_val++;
     } else if (individuals[ind_index]->give_fitness() <= 
           individuals[j]->give_fitness())
         s_val++;
   }
   
   individuals[ind_index]->set_score(s_val); 
      
  }

  /*
  ----------------- procedura QSort ---------------------------------------
  *** Scritta il: 15/9/03
  Questa procedura ordina gli individui della popolazione implementando l'
  algoritmo Quick Sort. Il primo individuo dell'ordinamento e' quello con 
  fitness piu' alta o piu' bassa, a seconda del problema. Il parametro type
  specifica se ordinare per problemi di massimizzazione o di minimizzazione.
  *** Ultima modifica: 
  */
  void Population::QSort(int left, int right, problem_types type)
  {
        int i, j;
        Individual *Pop_tt1, *Pop_tt2;

        i = left;
        j = right;
        Pop_tt1 = individuals[(left + right) / 2];

        // ----- Ordinamento per problemi di MASSIMIZZAZIONE -----
        if (type == max_)
          while( i <= j ) {
                while(individuals[i]->give_fitness() > Pop_tt1->give_fitness())
                        i = i + 1;
                while(Pop_tt1->give_fitness() > individuals[j]->give_fitness())
                        j = j - 1;
                if (i <= j) {
                        Pop_tt2 = individuals[i];
                        individuals[i] = individuals[j];
                        individuals[j] = Pop_tt2;
                        i = i + 1;
                        j = j - 1;
                }
          }

        // ----- Ordinamento per problemi di MINIMIZZAZIONE -----
        if (type == min_)
          while( i <= j ) {
                while(individuals[i]->give_fitness() < Pop_tt1->give_fitness())
                        i = i + 1;
                while(Pop_tt1->give_fitness() < individuals[j]->give_fitness())
                        j = j - 1;
                if (i <= j) {
                        Pop_tt2 = individuals[i];
                        individuals[i] = individuals[j];
                        individuals[j] = Pop_tt2;
                        i = i + 1;
                        j = j - 1;
                }
          }

        if(left < j)
                QSort(left, j, type);
        if(i < right)
                QSort(i, right, type);

        return;
  }
  

  /*
  ----------------- procedura QSort ---------------------------------------
  *** Scritta il: 15/9/03
  Questa procedura ordina gli individui della popolazione implementando l'
  algoritmo Quick Sort. Ordina in base allo score degli inviddui.
  *** Ultima modifica: 
  */
  void Population::QSort(int left, int right)
  {
        int i, j;
        Individual *Pop_tt1, *Pop_tt2;

        i = left;
        j = right;
        Pop_tt1 = individuals[(left + right) / 2];

          while( i <= j ) {
                while(individuals[i]->give_score() > Pop_tt1->give_score())
                        i = i + 1;
                while(Pop_tt1->give_score() > individuals[j]->give_score())
                        j = j - 1;
                if (i <= j) {
                        Pop_tt2 = individuals[i];
                        individuals[i] = individuals[j];
                        individuals[j] = Pop_tt2;
                        i = i + 1;
                        j = j - 1;
                }
          }

        

        if(left < j)
                QSort(left, j);
        if(i < right)
                QSort(i, right);

        return;
  }
  /*
  ----------------- Procedura give_params ---------------------------------
  *** Scritta il:
  Copia nel file passato come parametro quello che contiene i parametri.
  *** Ultima modifica: 
  */
  void Evolution::give_params(ofstream *out_stream)
  {
     ifstream *tmp_stream;   
  
      // Si apre il file passato come parametro.
     tmp_stream = new ifstream(file_name); 

     // Si controlla la corretta apertura del file.
     if (!*tmp_stream)
       *out_stream<<(char *) "\nATTENZIONE\nImpossibile aprire il file: "<<
                      file_name;

     // Si memorizzano i parametri evolutivi.
     file_copy(tmp_stream, out_stream);

     // Si chiude il file aperto.
     delete tmp_stream;
     
     
     return;
 }    

  
  /******************************************************************
          Definizione delle procedure della classe INDIVIDUAL
  ******************************************************************/

  /*
  ----------------- Procedura Individual ----------------------------------
  *** Scritta il:
  E' la costruttrice della classe.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Individual::Individual()
  {
     // L'individuo e' vivo!
     alive = true;


     return;
  }
 
  /*
  ----------------- Procedura Individual ----------------------------------
  *** Scritta il:
  E' la costruttrice della classe.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Individual::Individual(Evolution *e_ptr)
  {
     // L'individuo e' vivo!
     alive = true;
     
     // Si punta alla classe Evolution.
     evo_ptr = e_ptr;


     return;
  }
  /*
  ----------------- procedura update --------------------------------
  *** Scritta il:
  Aggiorna il fenotipo e ricalcola la fitness.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Individual::update()
  {
            
     // Riscrive il fenotipo.
     write_pheno();
        

     return;
  }
  
  /*
  ----------------- procedura show ----------------------------------------
  *** Scritta il:
  Mostra le variabili built-in dell'individuo. 
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Individual::show(ostream *out_stream)
  {
     int i;
     
     *out_stream<<endl<<"*********"<<endl;
     
     // Si visualizza il valore della fitness.
     *out_stream<<endl<<"fitness: "<<fitness<<endl;
     
     // Si visualizzano le variabili built-in utilizzate.
     for (i=0; i < built_ins.give_Num(); ++i)
     {
        *out_stream<<endl<<built_ins.give_full(i)<<" "<<inner_vars[i]; 
     }  

     
     *out_stream<<endl<<"*********"<<endl;


     return;
  }

/*
  ----------------- procedura comp_time --------------------------------
  *** Scritta il:
  Aggiorna il fenotipo e ricalcola la fitness.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  double Individual::comp_time()
  {
          
     if (evo_ptr != NULL)
       return time = ((double) clock() - ((double)evo_ptr->give_ini_time()))
                     / CLOCKS_PER_SEC;
     else abort_message((char *) "funzione Individual::comp_time: evo_ptr vale NULL! ");
  }


  
  /*
  ----------------- procedura give_fitness --------------------------------
  *** Scritta il:
  Restituisce il valore della fitness dell'individuo. 
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
 inline double Individual::give_fitness()
 {
    
    if (evo_ptr == 0)
      abort_message("Individual::give_fitness (evolution.cpp, row 859) \
              manca inizializzazione puntatore evo_ptr");
    
    // Si controlla se � vivo!
    if (alive)
      return fitness;     
    else if (evo_ptr->problem_type == max_)
           return numeric_limits<double>::min();
         else  return numeric_limits<double>::max();
   
 }
  
  /*
  ----------------- procedura give_val ------------------------------------
  *** Scritta il:
  Restituisce il valore della variabile built-in di indice index
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
 // inline double Individual::give_var(int index)
//  {
//               
//     // Restituisce il valore della variabile built-in richiesto.
//     return inner_vars[index];     
//  }
    

  /************************************************************************
            Definizione delle procedure della classe EVOLUTION
   ***********************************************************************/

  /*
  ----------------- Procedura Evolution  ----------------------------------
  *** Scritta il:
  E' la costruttrice della classe. E' vuota.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Evolution::Evolution()
  {
    e_type = gen;
    
    return;
  }

  /*
  ----------------- Procedura get_params ----------------------------------
  *** Scritta il:
  Legge da file i parametri dell'evoluzione da implementare. Alla procedura 
  viene passata la riga di comando per controllare se aprire il file di de-
  fault oppure un passato dall'utente.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Evolution::get_params(int argc, char *argv[])
  {
     FILE *file_ptr; 	  
     char line[MAX_CHAR_LINE], *line_ptr;
     int i,params, N_params;
     
     
     /* Si inizializza la stringa che deve contenere il nome del file dei 
       parametri. */ 
     for (i=0; i < MAX_CHAR_FILE_NAME; ++i)
        file_name[i] = '\0';   


     // Si verifica la riga di comando per comprendere quale file aprire.
     if (read_param(argc, argv, "-p", file_name))
       // Si apre il file passato dall'utente alla riga di comando.
       file_ptr = fopen(file_name, "r");
     // I parametri vanno letti dal file di default.
     else 
     {
       // Si copia il nome del file di default.
       strcpy(file_name, DEFAULT_EVO_FILE);
       
       // Si apre il file.
       file_ptr = fopen(file_name, "r");
     }   
       
           
     // Si controlla se il file e' stato aperto correttamente.
     if (file_ptr == NULL)
       abort_message("Impossibile aprire il file \"%s\" \n \
       per la lettura dei parametri!", file_name);     
     
     
     /* Prima si acquisisce il numero di parametri presenti nel file.
     get_line(line, file_ptr, MAX_CHAR_LINE);

     if (!get_int(line, "N_PARAMS", N_params))
       /* Se non si riesce ad acquisire il numero di paarmetri, il program-
          ma viene terminato. 
       abort_message("ERRORE ! Impossibile trovare \"N_PARAMS\" nel\
        file %s",file_name);


     /* Il ciclo che segue legge da file tutti i parametri dell'evo-
        luzione. */
     params = 0;

     while (get_line(line, file_ptr, MAX_CHAR_LINE)) /* && 
            (params < N_params))*/
     {
        if (extract_param(line) || extract_more_param(line))
          ++params;
        else abort_message("ERRORE durante la lettura del file %s",
                            file_name);
     }
   /*  if (params < N_params)
       abort_message("Il numero di parametri contenuto nel file %s e' \
       insufficiente", file_name);*/
     fclose(file_ptr);
     if (visual)
       printf("\n\nI parametri dell'evoluzione sono stati letti dal \
       file: %s", file_name);
     
     cout<<"\n parametri evolutivi letti dal file: "<<file_name<<endl;

     return;
  }

  /*
  ----------------- Procedura check_params --------------------------------
  *** Scritta il: 13/1/04
  Verifica se i valori dei parametri sono  dell'evoluzione minori dei valo-
  ri massimi consentiti.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Evolution::check_params()
  {
     /* Si verifica se il numero massimo di iterazioni e' maggiore del mas-
        simo consentito. */
     if (N_iters > MAX_ITERS)
       abort_message("Il parametro max_iters e' maggiore del numero \
       massimo consentito (%d), correggere il valore della costante \
       MAX_ITERS nel file evolimits.h", MAX_ITERS);

     /* Si verifica se il numero massimo di individui e' maggiore del mas-
        simo consentito. */
     if (N_inds > MAX_INDIVIDUALS)
       abort_message("Il parametro n_individual e' maggiore del numero \
       massimo consentito (%d), correggere il valore della costante \
       MAX_INDIVIDUALS nel file evolimits.h", MAX_INDIVIDUALS);
    
      /* Si verifica se il numero massimo di variabili e' maggiore del mas-
        simo consentito. */
     if (built_ins.give_Num() > MAX_VARS)
       abort_message("Il parametro n_vars e' maggiore del numero \
       massimo consentito (%d), correggere il valore della costante \
       MAX_INDIVIDUALS nel file evolimits.h", MAX_INDIVIDUALS);
       
     // **************** Si controlla il tournament ***************
     
     // Si verifica prima se il tournament e' usato oppure no.
     if ((selection== tournment) || (selection == tournment))
       if (tourn_size < 2)
         abort_message("La dimensione del torneo e' insufficiente!: %d", 
                     tourn_size); 
     
     // Si controllano le dimensioni dell'elitismo.
     if (elitism > N_inds)
     abort_message(" L'elitismo e' maggiore del numero di individui nella \
     popolazione!"); 

     return;
  }


  /*
  ----------------- Procedura extract_param -----------------------------
  *** Scritta il:
  Estrae dalla linea in input il parametro contenuto e lo assegna al re-
  lativo attributo.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  bool Evolution::extract_param(char *line)
  {
     char *line_ptr;     

     /* Si convertono i minuscolo tutti i caratteri presenti nella linea
        passata come parametro. */
     str_lwr(line, MAX_CHAR_LINE);
     

     // ***************** Numero di individui ******************************
     if (strstr(line, "n_individuals"))
       if (get_int(line, "n_individuals", N_inds))
          return true;
       else abort_message("ERRORE ! Nella lettura del parametro \
		       \"N_indiviuals\"!");
          
     // ***************** Tipo di problema *********************************
     if (strstr(line, "problem_type"))
       if (get_string(line, "problem_type", line_ptr))
       {
          if (strstr(line_ptr, "max"))
          {
            problem_type = max_;
	    
            return true;
          }

          if (strstr(line_ptr, "min"))
          {
	        problem_type = min_;
	    
            return true;
          }

          abort_message("ERRORE ! Nella lettura del parametro \
          \"problem_type\"!");
     }

     // *************** Percentuale massima di elitismo ******************
     if (strstr(line, "elitism"))
       if (get_int(line, "elitism", elitism))
	     return true;
       else abort_message("ERRORE ! Nella lettura del parametro \
		       \"elitism\"!");

 // ********************* Tournment  size **********************************
     if (strstr(line, "tourn_size"))
       if (get_int(line, "tourn_size", tourn_size)) {
         // Si memorizza il tournament come metodo di selezione  
         selection = tournment; 
    
         return true;
       } 
       else abort_message("ERRORE ! Nella lettura del parametro \
		       \"tourn_size\"!");

// ********************* Truncation percent******** *************************
     if (strstr(line, "trunc_size"))
       if (get_double(line, "trunc_size", trunc_size)) {
          // Si memorizza la truncation come metodo di selezione  
          selection = trunc_; 

         return true;
       }
       else abort_message("ERRORE ! Nella lettura del parametro \
		       \"trunc_size\"!");

 // *********************Numero di iterazioni ****************************
     if (strstr(line, "max_iters"))
       if (get_int(line, "max_iters", N_iters))
          return true;
       else abort_message("ERRORE ! Nella lettura del parametro \
		          \"max_iters\"!");

 // ********************** Probabilita' di crossover **********************
     if (strstr(line, (char *)"cross_prob"))
       if (get_float(line, "cross_prob", cross_prob))
         return true;
       else abort_message("ERRORE ! Nella lettura del parametro \
		          \"cross_prob\"!");

 // ********************** Probabilita' di mutazione **********************
     if (strstr(line, "mut_prob"))
       if (get_float(line, "mut_prob", mut_prob))
         return true;
       else abort_message("ERRORE ! Nella lettura del parametro \
		          \"mut_prob\"!");

// ********************** Range di mutazione ******************************
     if (strstr(line, "mut_range"))
       if (get_double(line, "mut_range", mut_range))
         return true;
       else abort_message("ERRORE ! Nella lettura del parametro \
		          \"mut_range\"!");

 // ********************** Tipo di selezione per il crossover ***************
     if (strstr(line, "selection"))
       if (get_string(line, "selection", line_ptr))
       {     

         if (strstr(line_ptr, "random"))
         {
           selection = rand_;
	   
           return true;
         }

         if (strstr(line_ptr, "wheel"))
         {
            selection = wheel;
	    
            return true;
         }

         if (strstr(line_ptr, "stoc_uni"))
         {
           selection = stoc_uni;
	         stoc_choose = true;
	   
           return true;
         }         

         abort_message("ERRORE ! Nella lettura del parametro \
		          \"selection\"!");
       }

       
     // ********************** Numero di individui per il SUS *************
     if (strstr(line, "sus_num"))
       if (get_int(line, "sus_num", sus_num))
          return true;
       else abort_message("ERRORE ! Nella lettura del parametro \
		          \"SUS_num\"!");

     // ********************** Tipo di obbiettivo *************************
     if (strstr(line, "target_type"))
       if (get_string(line, "target_type", line_ptr))
       {
         if (strstr(line_ptr, "super"))
         {
           target = super;
           
           return true;
         }

         if (strstr(line_ptr, "population"))
         {
           target = pop;
           
	       return true;
         }

         if (strstr(line_ptr, "subs"))
         {
            target = subs;
           
	        return true;
         }
         
         abort_message("ERRORE ! Nella lettura del parametro \
		          \"target_type\"!");
       }
  
       // ********************** Tipo di evoluzione *************************
     if (strstr(line, "evo_type"))
       if (get_string(line, "evo_type", line_ptr))
       {
         if (strstr(line_ptr, "gen"))
         {
           e_type = gen;
           
           return true;
         }

         if (strstr(line_ptr, "steady"))
         {
           e_type = steady;
           
	       return true;
         }   
         
         if (strstr(line_ptr, "gp"))
         {
           e_type = gp;
           
	       return true;
         } 
         
         abort_message("ERRORE ! Nella lettura del parametro \
		          \"evo_type\"!");
       }
     
     // ***************** Distanza per la stampa dei risultati *******
     if (strstr(line, "print_distance"))
       if (get_int(line, "print_distance", print_dist))
          return true;
       else abort_message("ERRORE ! Nella lettura del parametro \
		       \"print_distance\"!");
     
     
      // il parametro non � stato trovato.
      return false;
  }
  

  /*
  ----------------- procedura show_iter -----------------------------------
  *** Scritta il:
  Mostra i risultati ottenuti durante l'iterazione suul'output passato come
  parametro. 
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Evolution::show_iter(ostream *out_stream)
  { 
     /* Si apre il file dove stampare tutti i dati del run che vengono stam-
       pati anche a terminale. */
    
    
     
     /* Si controlla se i dati devono essere visualizzati, controllando 
        la variabile di visualizzazione. */
     if (visual)
     {
       /* Si verifica l'intervallo fra una visualizzazione ed un'altra. La 
          prima iterazione viene sempre visualizzata. */     
       if ((((iters_done % print_dist) == 0)) || (iters_done == 1))
       {                       
         *out_stream<<endl<<"Evoluzioni:"<<iters_done<<endl;
         // Si controlla se c'e' stato un miglioramento del best so far.
         if  ((new_best_so_far) || (iters_done == 0))
         {                       
           // Si visualizzano i dati relativi alla popolazione corrente. 
           curr_pop->show_data(out_stream);
           
           /* Si reinizializza la variabile che rappresenta il miglioramen-
              to del best so far. */    
           new_best_so_far = false;
         }    
         else *out_stream<<" fitness media: "<<curr_pop->average_fit;  
                                
       }
     }      
       /* Se i dati non devono essere visualizzati a terminale, si visualiz-
          za l'andamento del run. */
     else if ((N_iters > 50) && ((iters_done % (N_iters / 50)) == 0) &&
                (iters_done != 0))
            if ((iters_done % (N_iters / 5)) != 0 )
                *out_stream<<".";
            else *out_stream<<"|";
     
     // Si forza la scrittura del file.
     out_stream->flush();
     
                                       
      
  }
  /*
  ----------------- procedura find_super ----------------------------------
  *** Scritta il:
  Esegue l'algoritmo, alla ricerca di un superindividuo, generando una popo-
  lazione iniziale ed evolvendola fino a quando non si raggiunge uno dei 
  criteri di terminazione. Il parametro visual_mode indica se stampare a vi-
  deo i risultati parziali ottenuti.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Evolution::find_super(bool visual_mode)
  {
     Population *temp_pop_ptr;
     int i, tot_prob;
     double best_so_far_fit, curr_pop_best_fit;
     ofstream out_stream, run_stream;
     

     
     // Inizializzazione.
     visual = visual_mode;
     stoc_choose = false;
     new_best_so_far = false;
      

     // Si verificano i parametri dell'evoluzione caricati.
     check_params();
     
     // Si caricano le eventuali variabili built-ins.
     if (visual)
       built_ins.get_names(true);
     else built_ins.get_names(false);
     
     // Si verifica se e' stata generata la popolazione iniziale.
     if (curr_pop ==  NULL)
       abort_message("ERRORE: la popolazione iniziale non e' stata generata:\n \
       impossibile iniziare l'esecuzione dell'algoritmo!");
 
     // Si trova il miglior individuo della popolazione appena generata.
     curr_pop->find_best(problem_type);
        
     /* Bisogna allocare altre risorse per memorizzare il migliore indivi-
        duo. */
     best_so_far = curr_pop->best->build_copy();


     // ************** ESECUZIONE dell'algoritmo *****************
     
     if (visual)
     {
       printf("\n\nL'esecuzione dell'algoritmo e' iniziata ...\n");
       printf("La popolazione iniziale contiene %d individui ", curr_pop->ind_counter); 
     }    
     else cout<<endl<<".........|.........|.........|.........|.........|"<<endl;       
      

     iters_done = 0;
     best_iter = 0;
     ini_time = clock();

     while (!termination())
     {
       /* Si controlla che il numero di individui della popolazione sia
          quello giusto. */
       if (curr_pop->ind_counter < N_inds)
     	 abort_message("Il numero di individui della popolazione \
			            corrente non e' corretto!\n Iterazione \
            			numero: %d, numero di individui presenti: %d",
                iters_done, curr_pop->ind_counter);

       // Si ordina la popolazione corrente.
       curr_pop->QSort(0, curr_pop->ind_counter - 1, problem_type);       
      
               
       // Si trova il migliore individuo della popolazione corrente.
       curr_pop->find_best(problem_type);
        
       /* Si memorizzano le fitness del migliore della popolazione corrente
          e del best so far. */
       best_so_far_fit = best_so_far->give_fitness();
       curr_pop_best_fit = curr_pop->best->give_fitness();
       
       // Si effettuano i calcoli relativi solo all'individuo migliore.
       curr_pop->best->comp_data();
           
             
       /* Si controlla se e' stata migliorata la best_so_far, in tal caso,
          bisogna aggiornare la best_iter e la best so far. Il controllo
          viene fatto tenendo conto se si tratta di un problema di miniz-
          zazione o di massimizzazione. */
       if (((problem_type == max_ ) && (curr_pop_best_fit > 
             best_so_far_fit)) || ((problem_type == min_) &&
              (curr_pop_best_fit < best_so_far_fit)))
       {
	 
	 
         best_iter = iters_done;

         // Si cancella la copia del best so far precedente.
         best_so_far->kill();

         // Si crea un copia del nuovo best so far.
	     best_so_far = curr_pop->best->build_copy();
	     	        
	     /* Si aggiorna la variabile che memorizza i miglioramenti della 
	        best so far. */
         new_best_so_far = true;
       }
      // else new_best_so_far = false; prova
                      

       // ************** Visualizzazione dei risultati ********************
           
       // A terminale 
       show_iter(&cout);
          
 
       /* Si effettuano alcuni calcoli necessari all'esecuzione dell'algo-
          ritmo. */
       curr_pop->comp_data();

                
       /* Si chiama la procedura per la memorizzazione di tutti i dati rela-
          tivi all'iterazione appena effettuata. */
       memo_data_iter();
                             

       /* Se tra le modalita'di selezione per i vari operatori c'e' anche
          il tipo SUS, allora si costruisce la struttura dati necessaria
          alla sua esecuzione. */
       if (stoc_choose)
         curr_pop->build_sus_array(problem_type);
 
       /* Si evolve la popolazione corrente e si costruisce una nuova
          popolazione applicando gli operatori. */          
       
       if (e_type == steady) 
         build_steady_pop();
       else if (e_type == gen)
              build_next_pop();
            else build_next_pop2();
                  
       // Si eliminano gli individui della popolazione corrente.
       curr_pop->kill(); 
                               
       // Si aggiornano gli individui della nuova popolazione.
       next_pop->update(); 
                                    
     
       /* Si effettua lo scambio di puntatori alle popolazioni, cosicche'
          la nuova popolazione costruita diventi la popolazione corrente
          alla prossima iterazione. */
       temp_pop_ptr = curr_pop;
       curr_pop     = next_pop;
       next_pop     = temp_pop_ptr;


       // Incremento della variabile di ciclo.
       ++iters_done;
     }
     
     
     // Se in modalita' visuale si restituisce il prompt d'accapo
     if (visual)
       cout<<endl;
     // Si stampa l'ultimo trattino per la visualizzazione dell'andamento.  
     else 
     {
         cout<<"|";
         
         /* Si visualizza in un file dedicato la migliore soluzione  otte-
            nuta alla fine del run. 
         out_stream.open("evolution.dat", ios::app);
         best_so_far->show(&out_stream);
*/
          
         
     }    
     
     
     return;
  }


  /*
  ----------------- procedura build_next_pop -----------------------------
  *** Scritta il:
  Applica gli operatori di evoluzione alla popolazione corrente e la tras-
  forma in una nuova popolazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Evolution::build_next_pop()
  {
     int ind_num, i;
     Individual *input_ptr1, *input_ptr2, *output_ptr1, *output_ptr2,
                *tmp_ptr;
	
      
     
     // Si memorizza il numero di individui della popolazione corrente.
     ind_num = curr_pop->ind_counter;      

     // ************* Applicazione dell' ELITISMO *************************
     
     
     /* Si copiano i migliori individui della popolazione corrente nella 
        popolazione successiva. */
     for (i=0; i < elitism; ++i) {	     
	/* Si usa una variabile temporanea per puntare agli individui della
	   popolazione corrente. */
        input_ptr1 = curr_pop->individuals[i];
	// Si crea la copia
	output_ptr1 = input_ptr1->build_copy();
	// Si aggiunge l'individuo alla popolazione successiva. 
	next_pop->add_individual(output_ptr1);
	
     }
     
     /* Il ciclo for viene eseguito per un numero di volte pari al numero 
        di individui della popolazoine corrente meno quello degli individui
        che sono gia' stati copiati nella nuova popolazione per l'elitismo.
     */
     for (i = elitism; i < ind_num - 1; i+=2)
     {
        
	// *****************   FASE DI SELEZIONE   **************************
      
        /* Si scelgono due individui dalla popolazione corrente secondo
          le modalit� memorizzate negli attributi */
        input_ptr1 = curr_pop->select(selection, problem_type);
        input_ptr2 = curr_pop->select(selection, problem_type);


	// *****************   APPLICAZIONE DEL CROSSOVER   *****************

        /* Si chiama la procedura che applica il crossover agli individui 
           selezionati secondo la sua probabilita' di applicazione. */
        crossover->apply(input_ptr1, input_ptr2, output_ptr1,
                        output_ptr2);
      

	// ****************   APPLICAZIONE DELLA MUTAZIONE. ****************

	// *** Prima si applica al primo individuo. ***
        
        /* Si applica la mutazione che NON costruisce la copia, secondo la 
	       sua probabilita'. */
        mutation->apply(output_ptr1);
        next_pop->add_individual(output_ptr1);

                   		
        // *** Adesso si applica al secondo individuo. ***
        
        mutation->apply(output_ptr2);
        next_pop->add_individual(output_ptr2);
     } // FINE del ciclo di costruzione della popolazione successiva.
 
     
     /* Si controlla se bisogna aggiungere un altro individuo (il ciclo 
        precedente aggiunge un numero pari di individui). A quest'unico
	individuo si applica, eventualmente, la mutazione. */
     if (i == (ind_num - 1))
     {
       // Si seleziona l'individuo.
       input_ptr1 = curr_pop->select(selection, problem_type);
             
       // Se ne costruisce la copia
       tmp_ptr = input_ptr1->build_copy();
       
       // Si applica la mutazione
       mutation->apply(tmp_ptr);
       
       
       // Si applica la mutazione CON copia. PROVA
       // mutation->apply(input_ptr1, tmp_ptr);
       
       /* Si aggiunge la copia (eventualmente mutata) alla popolazione suc
          cessiva. */
       next_pop->add_individual(tmp_ptr);
     }
      

     return;
  }
  
  /*
  ----------------- procedura build_next_pop -----------------------------
  *** Scritta il:
  Applica gli operatori di evoluzione alla popolazione corrente e la tras-
  forma in una nuova popolazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Evolution::build_steady_pop()
  {
     int ind_num, i;
     Individual *input_ptr1, *input_ptr2, *output_ptr1, *output_ptr2,
                *tmp_ptr;
    Population *tmp_pop;
   
    
     // Si memorizza il numero di individui della popolazione corrente.
     ind_num = curr_pop->ind_counter;      

     /* Si genera un oggetto della classe Population per contenere la po-
        polazione temporanea. */
     tmp_pop = new Population(2*ind_num, this);

   

      /******************************************************************
      Si copia la popolazione corrente in quella temporanea. */

     for (i=0; i < ind_num; ++i)
     {	     
        /* Si usa una variabile temporanea per puntare agli individui della
	   popolazione corrente. */        
        input_ptr1 = curr_pop->individuals[i];
        
        // Si copia l'individuo.
        output_ptr1 = input_ptr1->build_copy();
	    tmp_pop->add_individual(output_ptr1);
     }     
	
     
     /* Il ciclo for viene eseguito per un numero di volte pari al numero 
        di individui della popolazoine corrente meno quello degli individui
        che sono gia' stati copiati nella nuova popolazione per l'elitismo.
     */
     for (i = 0; i < ind_num - 1; i+=2)
     {
        
	// *****************   FASE DI SELEZIONE   **************************
      
        // Si selezionano TUTTI gli individui della popolazione corrente.
        input_ptr1 = curr_pop->individuals[i];
        input_ptr2 = curr_pop->individuals[i+1];


	// *****************   APPLICAZIONE DEL CROSSOVER   *****************

        /* Si chiama la procedura che applica il crossover agli individui 
           selezionati secondo la sua probabilita' di applicazione. */
        crossover->apply(input_ptr1, input_ptr2, output_ptr1,
                        output_ptr2);
      

	// ****************   APPLICAZIONE DELLA MUTAZIONE. ****************

	// *** Prima si applica al primo individuo. ***
        
        /* Si applica la mutazione che NON costruisce la copia, secondo la 
	       sua probabilita'. */
        mutation->apply(output_ptr1);
        tmp_pop->add_individual(output_ptr1);

                   		
        // *** Adesso si applica al secondo individuo. ***        
        mutation->apply(output_ptr2);
        tmp_pop->add_individual(output_ptr2);
     } 
 
     
     /* Si controlla se bisogna aggiungere un altro individuo (il ciclo 
        precedente aggiunge un numero pari di individui). A quest'unico
	individuo si applica, eventualmente, la mutazione. */
     if (i == (ind_num - 1))
     {
       // Si seleziona l'individuo.
       input_ptr1 = curr_pop->individuals[i];
       
       // Se ne fa una copia // PROVA (17/12/2012)
        tmp_ptr = input_ptr1->build_copy();
        
        // si applica la mutazione 
        mutation->apply(tmp_ptr);
       
       // Si applica la mutazione CON copia.
       //mutation->apply(input_ptr1, tmp_ptr);
       
       /* Si aggiunge la copia (eventualmente mutata) alla popolazione suc
          cessiva. */
       tmp_pop->add_individual(tmp_ptr);
     }

     // Si calcolano gli score della popolazione temporanea.
     for(i=0; i < tmp_pop->ind_counter; ++i)
       tmp_pop->comp_score(i, problem_type);
    

     // Si ordina la popolazione temporanea in base allo score
     tmp_pop->QSort(0, tmp_pop->ind_counter - 1);
     
     // Adesso si copiano i migliori individui nella prossima popolazione
     for (i=0; i < ind_num; ++i)
     {	     
        /* Si usa una variabile temporanea per puntare agli individui della
	   popolazione corrente. */        
        input_ptr1 = tmp_pop->individuals[i];
        
        // Si copia l'individuo.
        output_ptr1 = input_ptr1->build_copy();
	    next_pop->add_individual(output_ptr1);
     }
   
     // Si distrugge la popolazione temporanea.
     tmp_pop->kill(); 

     return;
  }

  
  /*
  ----------------- procedura build_next_pop2 -----------------------------
  *** Scritta il:
  Applica gli operatori di evoluzione alla popolazione corrente e la tras-
  forma in una nuova popolazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Evolution::build_next_pop2()
  {
     int ind_num, i, crossed_num, mut_start, mut_num;
     Individual *input_ptr1, *input_ptr2, *output_ptr1, *output_ptr2,
                *tmp_ptr;
	
      
    	

     // Si memorizza il numero di individui della popolazione corrente.
     ind_num = curr_pop->ind_counter;


     // ************* Applicazione dell' ELITISMO *************************
     
     
     /* Si copiano i migliori individui della popolazione corrente nella 
        popolazione successiva. */
     for (i=0; i < elitism; ++i) {	     
	/* Si usa una variabile temporanea per puntare agli individui della
	   popolazione corrente. */
        input_ptr1 = curr_pop->individuals[i];
	// Si crea la copia
	output_ptr1 = input_ptr1->build_copy();
	// Si aggiunge l'individuo alla popolazione successiva. 
	next_pop->add_individual(output_ptr1);
     }

     
     // Si calcola il numero di individui da utlizzare per il crossover.
     crossed_num = (int) (cross_prob * (ind_num - elitism));

     // *****************   APPLICAZIONE DEL CROSSOVER   *****************
     
     for (i = elitism; i < (elitism + crossed_num) - 1; i+=2)
     {
        
	    // SELEZIONE 
           
        /* Si scelgono due individui dalla popolazione corrente secondo
          le modalit� memorizzate negli attributi */
        input_ptr1 = curr_pop->select(selection, problem_type);
        input_ptr2 = curr_pop->select(selection, problem_type);


        /* Si chiama la procedura che applica il crossover agli individui 
           selezionati secondo la sua probabilita' di applicazione. */
        crossover->apply(input_ptr1, input_ptr2, output_ptr1,
                        output_ptr2);
        // Si aggiungono gli individui alla popolazione successiva.
       next_pop->add_individual(output_ptr1);
       next_pop->add_individual(output_ptr2);      
     }     
	 
   
     // ****************   APPLICAZIONE DELLA MUTAZIONE. ****************
     
     mut_start = elitism + crossed_num;
     mut_num   = (int) (mut_prob * (ind_num - elitism));
     
     while ( i++ < mut_start + mut_num) { 
	// *****************   FASE DI SELEZIONE   **************************
      
        /* Si scelgono due individui dalla popolazione corrente secondo
          le modalit� memorizzate negli attributi */
        input_ptr1 = curr_pop->select(selection, problem_type);
        
        // Se ne fa una copia // PROVA (17/12/2012)
        tmp_ptr = input_ptr1->build_copy();
        
        // si applica la mutazione 
        mutation->apply(tmp_ptr);
        
               
        // Si applica la mutazione CON copia.
       //mutation->apply(input_ptr1, tmp_ptr);

       // Si aggiunge l'individuo alla popolazione successiva.
       next_pop->add_individual(tmp_ptr);
     }    
   
     
     /* Si controlla se bisogna aggiungere un altro individuo (il ciclo 
        precedente aggiunge un numero pari di individui). A quest'unico
	individuo si applica, eventualmente, la mutazione. */
     while (i++ < ind_num) { //if (i < ind_num)     
       //for( ;i <= ind_num; ++i)
       
          // Si seleziona l'individuo.
          input_ptr1 = curr_pop->select(selection, problem_type);
             
          // Se ne fa una copia // PROVA (17/12/2012)
        tmp_ptr = input_ptr1->build_copy();
        
        // si applica la mutazione 
        //mutation->apply(tmp_ptr);
        
        // Si applica la mutazione CON copia.
        //mutation->apply(input_ptr1, tmp_ptr);
       
          /* Si aggiunge la copia (eventualmente mutata) alla popolazione suc
             cessiva. */
          next_pop->add_individual(tmp_ptr);
       }
 

     return;
  }


  /* 
  ----------------- procedura memo_data_iter ------------------------------
  *** Scritta il:
  Memorizza in array che si trovano all'interno degli oggetti della classe
  i dati specifici di ogni iterazione eseguita. Questi dati possono essere
  utilizzati a fini statistici.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Evolution::memo_data_iter()
  {
       
     // Si memorizza la fitness media dell'iterazione corrente.
     avefit_story[iters_done]  = curr_pop->average_fit;
      
     
     /* Se il problema e' la ricerca di un super individuo si memorizza la 
        fitness del miglior individuo della popolazione corrente. */
     bestfit_story[iters_done] = curr_pop->best->give_fitness();
     
     /* Si memorizzano le variabili built-in di cui bisogna tener conto, 
        chiamando la procedura specifica della classe Population che effet-
        tua i calcoli necessari. Come parametri si passano il numero di va-
        riabili e l'array dove memorizzarle. */
     curr_pop->comp_vars(built_ins.give_Num(), vars_story[iters_done]);
     
     
     return;
  }


  /*
  ----------------- Procedura show_data -----------------------------------
  *** Scritta il:
  Mostra i dati specifici dell'iterazione appena eseguita sull'output pas-
  sato come parametro. 
  *** Ultima modifica: ore 16.00 del 04/04/03
  */ 
  void Population::show_data(ostream *out_stream)
  {
     
    *out_stream<<" Best fit: "<<best->give_fitness()<<" fitness media: "
               <<average_fit;
    cout<<" best: ";
    best->show(out_stream);
       

   return;
  } 
  
  /*
  ----------------- Procedura get_evo_ptr ---------------------------------
  *** Scritta il:
  Acquisisce il puntatore passato parametro.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */ 
  void Population::get_evo_ptr(Evolution *evo_ptr)
  {

     /* Il puntatore passato come parametro viene memorizzato nella vari-
        abile che punta all'oggetto della classe Population. */
     evolution = evo_ptr;
     
     return;
  }


  /* 
  ----------------- procedura termination ---------------------------
  *** Scritta il:
  Controlla se sono verificati i criteri di terminazione dell'algori-
  tmo. Quello classico e'il numero massimo di evoluzioni ma possono
  essere aggiunti altri criteri
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  bool Evolution::termination()
  {
   if (iters_done == N_iters)
     return true;
   else return false;
  }	
  
  
  



  
  /*************************************************************************
          Definizione delle procedure della classe CROSSOVER
  *************************************************************************/
  
  
  /* 
  ----------------- procedura Crossover ------------------------------------
  *** Scritta il:
  E' la costruttrice della classe, e' vuota. 
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Crossover::Crossover()
  {
  
  
     return;
  }
  
  /*----------------- procedura give_cut --------------------------------
    *** Scritta il: 19/12/03
   Dati due individui, due individui (di qualsiasi tipo, ma con lunghezza 
   variabile) calcola i punti di taglio t1 e t2 in maniera tale che lun-
   ghezza dei figli sia sia compresa tra len1 e len2. Il parametro delta,
   indica quanto puo' spostarsi la lunghezza dei figli rispetto a quella 
   dei genitori. 
  */
   void Crossover::give_cut(int len1, int len2, int &cut1, int &cut2, int delta)
   {
     // Il primo punto di taglio viene scelto sull'individuo piu' corto. 
     if (len1 <= len2)
     { 
       cut1 = rnd(1, len1 - 1);
       
       cut2 = rnd(cut1 - delta, cut1 + len2 - len1 + delta);
     }
     else
     {
       cut2 = rnd(1, len2 - 1);
       
       cut1 = rnd(cut2 - delta, cut2 + len1 - len2 + delta);  
     }
     
     
     return;
   }

  
  /*************************************************************************
          Definizione delle procedure della classe MUTATION
  *************************************************************************/
  
  
  /* 
  ----------------- procedura Mutation -------------------------------------
  *** Scritta il:
  E' la costruttrice della classe, e' vuota. 
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Mutation::Mutation()
  {
  
  
     return;
  }
  /*
  ----------------- Procedura apply ---------------------------------------
  *** Scritta il: 01/03/04
  Applica l'operatore di mutazione alla multilista dell'individuo passato
  come parametro. Si costruisce prima la copia dell'individuo in input e
  poi si applica l'operatore sulla copia. Il puntatore alla copia cosi' mo-
  dificata viene memorizzato nel parametro output_ptr.
  *** Ultima modifica:
  */
  void Mutation::apply(Individual *input_ptr, Individual* &output_ptr)
  {
     /* Si costruisce la copia dell'individuo in input. Il casting e' ne-
       cessario, per effettuare la chaiamata specifica della classe Multi_
       individual. */


     output_ptr = input_ptr->build_copy();

     // Si chiama la procedura di mutazione
     mutate(output_ptr);

     return;
   }
   
   /*
  ----------------- Procedura apply ---------------------------------------
  *** Scritta il: 01/03/04
  Applica l'operatore di mutazione alla multilista dell'individuo passato
  come parametro, SENZA costruire la copia.
  *** Ultima modifica:
  */
  void Mutation::apply(Individual* input_ptr)
  {
    
    // Chiama la procedura di mutazione 
    mutate(input_ptr);

    return;
  }
   
  /************************************************************************
          Definizione delle procedure della classe FITNESS
   ***********************************************************************/

  /*
  ----------------- procedura Fitness -------------------------------------
  *** Scritta il: 19/12/03
  E' la procedura costruttrice della classe. E'vuota.
  */
  Fitness::Fitness()
  {


     return;
  }

  /*
  ----------------- procedura Fitness -------------------------------------
  *** Scritta il: 19/12/03
  E' la procedura costruttrice della classe. Il parametro specifica se st
  ampare l'avvenuta acquisizione.
  */
  Fitness::Fitness(bool visual_type)
  {
     visual = visual_type;

     return;
  }

  /*
  ----------------- Procedura get_params ----------------------------------
  *** Scritta il:
  Legge da file i parametri dell'evoluzione da implementare  e li assegna 
  agli attributi della classe. Il parametro � il ome del file che contiene 
  i paarmetri da leggere.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Fitness::get_params(int argc, char *argv[])
  {
     FILE *file_ptr; 	  
     char line[MAX_CHAR_LINE];
     int i, params, N_params;
 
     
     /* Si inizializza la stringa che deve contenere il nome del file dei 
       parametri. */ 
     for (i=0; i < MAX_CHAR_FILE_NAME; ++i)
        file_name[i] = '\0';
        
     // Si verifica la riga di comando per comprendere quale file aprire.
     if (read_param(argc, argv, "-f", file_name))
       // Si apre il file passato dall'utente alla riga di comando.
       file_ptr = fopen(file_name, "r");
     // I parametri vanno letti dal file di default.
     else 
     {
       // Si copia il nome del file di default.
       strcpy(file_name, DEFAULT_FIT_FILE);
       
       // Si apre il file.
       file_ptr = fopen(file_name, "r");
     }       
            
     // Si controlla se il file e' stato aperto correttamente.
     if (file_ptr == NULL)
       abort_message("Impossibile aprire il file \"%s\" \n \
       per la lettura dei parametri della fitness!", file_name);  
    
 
     // Si acquisisce il numero di parametri presenti nel file.
     get_line(line, file_ptr, MAX_CHAR_LINE);

     if (!get_int(line, "N_PARAMS", N_params))
       /* Se non si riesce ad acquisire il numerodi parametri il programma
          viene terminato. */
       abort_message("ERRORE ! Impossibile trovare \"N_PARAMS\" nel\
        file %s", file_name);


     params = 0;

     while ((get_line(line, file_ptr, MAX_CHAR_LINE)) && 
            (params < N_params))
     { 
        if (extract_param(line))
          ++params;
        else abort_message("ERRORE durante la lettura del file %s",
                            file_name);
     }
     if (params < N_params)
       abort_message("Il numero di parametri contenuto nel file %s e' \
                      insufficiente", file_name);
     fclose(file_ptr);
     
     if (visual)
       printf("\n\nI parametri della fitness sono stati letti dal \
		       file: %s", file_name);

     return;
  }


  /*
  ----------------- Procedura extract_param -----------------------------
  *** Scritta il:
  Estrae dalla linea in input il parametro contenuto e lo assegna al re-
  lativo attributo.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  bool Fitness::extract_param(char *line)
  {
     char *line_ptr;
     int w_num;

     if (strstr(line, "min_fitness"))
       if (get_double(line, "min_fitness", min))
          return true;
       else abort_message("ERRORE ! Nella lettura del parametro \
		       \"min_fitness\"!");
     
     // E' stato letto un parametro di tipo peso.
     if (line_ptr = strstr(line, "weight"))
     { 
         
       // Si avanza il puntatore.
       line_ptr += 6;
       
       // Si acquisisce il numero del peso.
       w_num = atoi(line_ptr);
       
       // Si controlla il valore del peso.
       if (w_num < 10)
       {       
         // Si incrementa il puntatore alla stringa.
         line_ptr += 2;
       
         // Si memorizza il valore del peso.
         weights[w_num] = atof(line_ptr); 
          
         return true;
       }
       else 
       { 
         cout<<"Questa linea e' sbagliata:"<<endl;
         cout<<line<<endl;
         cout<<"l'intervallo e': weight0-weight9"<<endl;
         return false;
       }       
     }       

     return false;
  }
  
  
  /*
  ----------------- Procedura give_params ---------------------------------
  *** Scritta il:
  Copia nel file passato come parametro i parametri della fitness.
  *** Ultima modifica: 
  */
  void Fitness::give_params(ofstream *out_stream)
  {
     ifstream *tmp_stream;   
    
      // Si apre il file che contiene i parametri della fitness.
     tmp_stream = new ifstream(file_name); 
     
     
     // Si controlla la corretta apertura del file.
     if (!*tmp_stream)
       *out_stream<<"\nATTENZIONE\nImpossibile aprire il file: "<<
                      file_name;

     // Si memorizzano i parametri nel file passato come parametro. 
     file_copy(tmp_stream, out_stream);

     // Si chiude il file aperto.
     delete tmp_stream;
     
     *out_stream<<endl<<endl;
     
     // Si visualizzano le eventuali informazioni specifiche.
     show(out_stream);
     
     
     return;
 }    
 
   

 /************************************************************************
          Definizione delle procedure della classe VARIABLES
   ***********************************************************************/

  /*
  ----------------- procedura Variables -----------------------------------
  *** Scritta il: 19/12/03
  E' la procedura costruttrice della classe. E'vuota.
  */
  Variables::Variables()
  {


     return;
  }
  
  /*
  ----------------- procedura get_names -----------------------------------
  *** Scritta il: 19/12/03
  Carica dal file "names.txt" i nomi da associare alla variabili e il loro
  numero. 
  */
  void Variables::get_names(bool visual)
  {
  
     ifstream in_stream;	  
     char line[MAX_CHAR_LINE], *line_ptr;
     int i,names, pos;
     
     
     // Si apre il file che contiene i nomi.
     in_stream.open("names.txt");  
           
     /* Si controlla se il file e' stato aperto correttamente. Se il file
        non esiste, allora significa che le variabili built-in non vengono
        usate. */ 
     if (!in_stream)
     {
       Num = 0;
       
       return;
     }
     
     /* Si inizializza il vettore relativo alla visualizzazione di massimi
        e minimi. */
     for (i=0; i < MAX_VARS; ++i)
        max_min[i] = false;   
            
     
     // Prima si acquisisce il numero di parametri presenti nel file.
     get_line(line, &in_stream, MAX_CHAR_LINE);

     if (!get_int(line, "N_NAMES", Num))
       /* Se non si riesce ad acquisire il numero di paarmetri, il program-
          ma viene terminato. */
       abort_message("ERRORE ! Impossibile trovare \"N_NAMES\" nel\
        file \" names.txt\"");


     /* Il ciclo che segue legge da file tutti i parametri dell'evo-
        luzione. */
     names = 0;
     

     while ((get_line(line, &in_stream, MAX_CHAR_LINE)) && (names < Num))
     {
        fulls[names] = line;
        
        /* Si controlla se e' presente l'asterisco: in tal caso bisogna vi-
           sualizzare anche massimo e minimo. */
        pos = fulls[names].find("*"); 
        
        if (pos != string::npos)
          max_min[names] = true; 
        
        // Si incrementa la variabile names.
        ++names; 
     }
     
     if (names < Num)
       abort_message("Il numero di variabili contenuto nel file \"names.txt\" \
        e' insufficiente");
     
     // Si chiude il file.
     in_stream.close();
     
     // Si calcolano le abbreviazioni. 
     comp_shorts();
     
     
     // Se e' il caso, si visualizza l'esito dell'operazione.
     if (visual)
       printf("\n\nI nomi delle variabili sono stati letti correttamente\n");

     return;
  }
  
  /*
  ----------------- procedura give_Num ------------------------------------
  *** Scritta il: 19/12/03
  Restituisce il numero di variabili built-in utilizzate.
  */
  inline int Variables::give_Num()
  {
      
      return Num;
  }
  
  /*
  ----------------- procedura comp_shorts ---------------------------------
  *** Scritta il: 19/12/03
  Calcola le abbreviazioni dei nomi delle variabii.
  */
  void Variables::comp_shorts()
  {
     int i;
     
     for (i=0; i < Num; ++i)
        comp_short(i);
        
        
     return;    
  }  
  
  /*
  ----------------- procedura comp_shorts ---------------------------------
  *** Scritta il: 19/12/03
  Calcola l' abbreviazione della variabile di indice index.
  */
  void Variables::comp_short(int index)
  {
      
     string::iterator short_it, full_it;    
     int full_len, jump, i, j;
      
      
     //  **** Inizializzazione ****
      
     // Si inizializza l'abbreviazione.
     shorts[index] = "   ";
      
     // Si inizializza la lunghezza della full.
     full_len = fulls[index].size();      
     jump = full_len / 3;
     
     // Il jump deve essere almeno di 2.
     if (jump == 1)
       jump = 2;
      
      
     // Si inizializzano gli iteratori.      
     full_it  = fulls[index].begin();
     short_it = shorts[index].begin();
      
     for (i=0; (i < 3) && (full_it != fulls[index].end()); ++i)
     {
        *short_it++= *full_it;
         
        // Si incrementa l'iteratore alla stringa che full.
        for (j=0; (j < jump)&&(full_it!=fulls[index].end()); ++j)
           ++full_it;
        
     //  short_it++;
     }
      
       
     return ;  
  }  
  


  /*
  ----------------- procedura give_full -----------------------------------
  *** Scritta il: 19/12/03
  Restituisce la stringa che contiene il nome completo della variabile di 
  indice index. 
  */
  string Variables::give_full(int index)
  {
      
    
    return fulls[index];  
  }  
  
  
  /*
  ----------------- procedura give_short ----------------------------------
  *** Scritta il: 19/12/03
  Restituisce la stringa ceh contiene il nome abbreviato della variabile di 
  indice index. 
  */
  string Variables::give_short(int index)
  {
      
    
    return shorts[index];  
  }  
  
  /*
  ----------------- procedura show_legend ---------------------------------
  Scritta il: 16/1/04
  Questa procedura visualizza la legenda delle variabili built-in nel file
  passato come  parametro.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Variables::show_legend(ofstream *out_stream)
  {
     int i; 
     
     
     *out_stream<<endl<<endl<<"  ***** LEGENDA ****"<<endl<<endl; 
      
     for (i=0; i < Num; ++i)
     {  
        *out_stream<<endl;
        *out_stream<<"VARIABILE: "<<give_full(i); 
        *out_stream<<endl<<"best:  "<<"b_"+give_short(i);    
        *out_stream<<endl<<"media: "<<"a_"+give_short(i);

        /* Si controlla se per l'i-esima variabile bisogna visualizzare an-
           che il massimo e il minimo. */
        if (max_min[i])
        {   
          *out_stream<<endl<<"max:   "<<"x_"+give_short(i);
          *out_stream<<endl<<"min:   "<<"n_"+give_short(i);
        }      
        *out_stream<<endl;
     }    

     return;
  }	
      
      
      
